package 面试刷题.小米;

import java.io.*;

/**
 * 离线
 * https://www.nowcoder.com/questionTerminal/96bf0c548a094de7a05919e0b32b1a5a?f=discussion
 *
 */
public class ch01_密码生成 {
    static int maxn = (int) (15000000 + 10);
    static int[] arr = new int[maxn];
    static int[] end = new int[maxn];
    static int n, m;
    static int mod = 100000009;

    public static void main(String[] args) {
        Reader2 sc = new Reader2(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int[][] queue = new int[m + 1][3];
        for (int i = 1; i <= m; i++) {
            queue[i][0] = sc.nextInt();
            queue[i][1] = sc.nextInt();
            queue[i][2] = i;
        }
        for (int i = queue.length - 1; i > 0; i--) {
            int l = queue[i][0];
            int r = queue[i][1];
            int v = queue[i][2];
            while (l <= r) {
                if (end[l] == 0) {
                    arr[l] = v;
                    end[l] = r;
                } else {
                    /*如果l碰到了已经加过的区间，则跳到该区间的末尾后一位*/
                    l = end[l];
                    if (r < l) {
                        end[queue[i][0]] = l;
                    }
                }
                l++;
            }
        }
        long res = 0;
        for (int i = 0; i < n; i++) {
            res += (long) i * arr[i];
            res %= mod;
        }
        System.out.println(res);
    }

    static class Reader2 {
        static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        public Reader2(Object... o) {
        }

        public int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {
            }
            return (int) in.nval;
        }
    }

}
